\section{Interconnect and Cost Models}\label{sec:model}
Metal layers can be reduced to achieve cost-efficient design in our proposed framework. In order to reduce metal layer in 3D designs, we need to estimate the minimum metal layer requirement that can guarantee the routability given the design gate count. Besides the interconnect model, 3D system cost models for TSV and interposer-based 3D ICs are necessary for cost analysis. In this section, the related interconnect model and 3D cost model are introduced. In the interconnect model, we describe how to estimate the die area and minimum metal layers for feasible routing, when only limited information are available. The second part of this section introduces a comprehensive 3D cost model that considers the area overhead and yield impact of TSV bonding, and the fabrication overhead of interposer stacking. These models facilitate the cost-driven 3D design flow in Section~\ref{sec:mechanism}.

\subsection{Interconnect Model}
The die area, which is defined as the area occupied by the transistors and the interconnects, is closely related to the gate count in designs~\cite{weerasekera2007}. However, in physical circuit designs, gates are not placed tightly with other, which introduces an area utilization rate to indicate the placement density. So the die area can be estimated as a function of the gate counts and area utilization rate:

\begin{equation}
A_{die} = \frac{N_gA_g}{A_{util}} \label{eq:corearea}
\end{equation}
where $N_g$ is the number of gates in the design, $A_g$ is an empirical parameter that represents the relation between single gate area and feature size, $A_{util}$ is the area utilization rate. In our work, $A_g$ is assumed to be $3125\lambda^2$, and $\lambda$ is half of the feature size.

The required metal layers for feasible routing highly depends on the placement and routing methodology, however, the detailed information are unavailable at the early design stage. In this model, we mainly analyze the relation between routing demand and routing resource to determine the required metal layers. 
A wire length distribution model based on Rent's rule is used to perform the routing demand estimation~\cite{Davis1998}. The wire length distribution equations with respect to the interconnect segment length $l$ is as follows:

Region I: $1\leq l \leq  \sqrt{N_g}$
\begin{equation}
i(l)=\frac{\alpha k}{2}\Gamma \left(\frac{l^3}{3}-2\sqrt{N_g}l^2+2N_gl\right)l^{2p-4}
\label{eq:wirei}
\end{equation}

Region II: $\sqrt{N_g}\leq l <   2\sqrt{N_g}$
\begin{equation}
i(l)=\frac{\alpha k}{6}\Gamma \left( 2\sqrt{N_g}-l\right)^3l^{2p-4}
\label{eq:wireii}
\end{equation}
where $k$ is Rent's coefficient, represents the average number of pins per block and $p$ is Rent's exponent~\cite{rentsrule} within the range of 0.4 to 0.9~\cite{christie2000}. $\alpha = \frac{f.o.}{f.o. + 1}$ is related to the average fanout of a gate to represent the proportion of on-chip sink terminals. $\Gamma$ is given as follows:

\begin{equation}
\Gamma = \frac{2N_g\left(1-N_g^{p-1} \right )}{\left(-N_g^p\frac{1+2p-2^{2p-1}}{p(2p-1)(p-1)(2p-3)}-\frac{1}{6p}+\frac{2\sqrt{N_g}}{2p-1}-\frac{N_g}{p-1} \right )}
\label{eq:gamma}
\end{equation}

For any given interconnect length, the accumulative number of interconnects $I(l)$, which means the number of interconnects with length smaller or equal to $l$, can be derived from the cumulative integral of the wire length distribution function $i(l)$. The accumulative routed wire length $L(l)$, which denotes the routing demand, is given as the first-order moment of $i(l)$.

To this end, one of the two components in interconnect model, the routing demand, has been analyzed. The routing resource is related to the available routing area and wire pitches. The available signal routing resource is significantly smaller than the total track length on all metal layers because of the routing efficiency, the impact of the vias, and the resource occupied by power, ground, and clock distribution~\cite{kahng01}. The available signal routing resource for each metal layer is given as follows:

\begin{equation}
K_i = \frac{A_{die}\eta_i-2A_v\left(I(l_{max})-I(l_i) \right )}{\omega_i}
\label{eq:routesource}
\end{equation}
where $A_{die}$ is the die area given in equation~\ref{eq:corearea}, $\eta_i$ is the metal layer utilization, $A_v$ and $\omega_i$ are the via area and wire pitches on metal layer $i$, $l_{max}$ and $l_i$ are the maximum single wire length on the whole chip and one metal layer. 

With this interconnect model, we are assuming the shorter interconnects are routed first on lower metal layers. The routing process starts from bottom metal layer, and moves up the higher metal layers only when the bottom layers are fully utilized. Furthermore, for each metal layer, the total routed wire length cannot exceed the available routing resource. The required metal layers are derived from repeating this process until all the wires are properly assigned to metal layers.

\subsection{3D Cost Model}
The cost models are different in TSV-based and interposer-based designs.  The cost of 3D TSV-based ICs contains two parts: wafer cost and bonding cost. Wafer cost captures the wafer cost with related die cost and die yield, similar to the cost in traditional 2D designs. Bonding cost models the cost overhead of TSV bonding, including wafer thinning, TSV forming, and die bonding, which is unique in 3D designs. In our work, the interposer is treated as regular silicon device, therefore, only the wafer cost is considered.

\textit{Wafer Cost Model}. In the wafer cost part, the most important factor is the die area. The die area estimations of TSV-based and interposer-based structure are different. TSV-based structure introduces area overhead, because the silicon area where TSVs are built cannot be utilized. Normally, the diameter of TSVs is large compared to the transistor feature size and it can range from $1\mu m$ to $10 \mu m$~\cite{Loh2007}. The area overhead can be estimated through the euqation $A_{3D} = A_{die} + N_{TSV/die} * A_{TSV}$~\cite{xiangyu2010}. $N_{TSV/die}$ refers to the number of TSVs on each die, $A_{TSV}$ is the area of TSV and it can be calculated from the TSV pitch, and $A_{3D}$ is the final die area of one 3D stacking die.

For interposer-based structure, the vertical interconnects have no impact on chip area because the TSVs are fabricated inside the interposer. So the die area can be estimated directly from Equation~\ref{eq:corearea}. Given the die area and wafer diameter, the wafer utilization in terms of number of dies per wafer can be calculated.

Besides the wafer utilization, the die yield also influences the cost, which is formulated as follows:
\begin{equation}
Y_{die} = Y_{wafer} * \frac{1 - e^{-2A_{die}D_0}}{2A_{die}D_0}\label{dieyield}
\end{equation}
where $D_0$ is the defect density of the wafer, $Y_{die}$ and $Y_{wafer}$ are the die yield and wafer yield, respectively.

Since 3D integration enables heterogeneous stacking, the chip size of stacking dies can be different. The overall die yield can be calculated by multiplying the individual yield of each die in the stacking.

\textit{3D Bonding Cost}. In order to build 3D stacking, extra fabrication steps are needed, including wafer thinning, TSV forming, and die bonding. These process steps have impact on bonding cost: wafer thinning decreases the wafer yield; TSV forming increases the process cost; and die bonding influences both the process cost and stacking yield. The total stacking yield is a function of the TSV number ($N_{TSV}$) and the single TSV yield ($Y_{TSV}$), and it can be calculated by  $Y_S = Y_{bonding} * Y_{TSV}^{N_{TSV}}$~\cite{chen2010}. The TSV number can be estimated as follows at the early design stage:
\begin{eqnarray}
N_{TSV} = \alpha k_{1,2}(B_1 + B_2)(1-(B_1 + B_2)^{p_{1,2}-1})  \nonumber \\
- \alpha k_1B_1\left( 1-B_1^{p_1- 1}\right) - \alpha k_2 B_2\left( 1-B_2^{p_2- 1}\right)
\end{eqnarray}
where $B_1$ and $B_2$ are the number of blocks in two tiers, $k_{1,2}$ and $p_{1,2}$ are the equivalent Rent's coefficient and exponent.

\textit{Overall 3D Cost Model}. 
The TSV-based cost combines the wafer cost and the bonding cost. 
%For die-to-wafer stacking, the individual dies are cut from wafer first and then stack on the bottom wafer after testing. So only the known-good-dies are put into the stacking. On the other hand, for wafer-to-wafer stacking, wafers are bonded together before testing, so die yield and stacking yield have impacts on the final fabrication yield. 
In our work, we only consider die-to-wafer stacking, the TSV-based 3D cost ($C_{T3D}$) can be calculated from:
\begin{eqnarray}
C_{T3D}& =& \frac{\frac{\sum_{i=1}^{N}(C_{die_i}+ C_{KGDtest})}{Y_{die_i}}+(N-1)C_{bonding}}{Y_S^{(N-1)}} 
%C_{W2W} &= &\frac{\sum_{i=1}^{N}C_{die_i}+(N-1)C_{bonding}}{(\prod_{i=1}^{N}Y_{die_i})Y_S^{N-1}}
\end{eqnarray}
where $C_{bonding}$ is the bonding cost, which captures the wafer thinning, TSV forming, and bonding cost. 

The interposer-based structure cost only contains the wafer cost model. And we only consider the case shown in Figure~\ref{fig:3dinterposer}(b) where two known good dies stack on both sides of an interposer. In this scenario, the overall cost of one interposer stacking ($C_{I3D}$) is given as follows:
\begin{equation}
C_{I3D} = \sum_{i=1}^{N}(C_{die_i}+C_{KGDtest}) + \sum_{i=1}^{N/2}C_{interposer} \label{eq:intercost}
\end{equation}
where $N$ is the number of tiers in the 3D design, $C_{die_i}$, $C_{interposer}$ are the cost of each die in the stacking and interposer wafer cost, respectively, $C_{KGDtest}$ is the testing cost for each die.